package com.fucius.study.leetcode;

/**
 * 3. 统计数字
 * 中文English
 * 计算数字 k 在 0 到 n 中的出现的次数，k 可能是 0~9 的一个值。
 *
 * 样例
 * 样例 1：
 *
 * 输入：
 * k = 1, n = 1
 * 输出：
 * 1
 * 解释：
 * 在 [0, 1] 中，我们发现 1 出现了 1 次 (1)。
 * 样例 2：
 *
 * 输入：
 * k = 1, n = 12
 * 输出：
 * 5
 * 解释：
 * 在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 中，我们发现 1 出现了 5 次 (1, 10, 11, 12)(注意11中有两个1)。
 */
public class DigitCounts {
    /**
     * 时间复杂度O(lgN)
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    public int digitCounts(int k, int n) {
        if (k>9||k<0||n<0) {
            return 0;
        }
        int i =0,j=0,m=n;
        int result = 0;
        do{
            j=m%10;
            m=m/10;
            int z = (int)Math.pow(10,i-1);
            if(j<k){
                result = result + j*i*z;
            }else if(j==k){
                int x = (int)Math.pow(10,i+1);
                int y = (int)Math.pow(10,i);
                int h = n%x;
                result = result + j*i*z + (h-j*y+1);
            }else{
                int y = (int)Math.pow(10,i);
                result = result + j*i*z + y;
            }
            i++;
        }while (m>0);
        //0比较特殊
        if (k==0) {
            for (int l = 0; l < i; l++) {
                result = result - (int)Math.pow(10,l);
            }
            result +=1;
        }

        return result;
    }
}
